
//
//  BinaryTreeNode.swift
//  SwiftyDSA
//
//  Created by Archer on 2018/8/9.
//  Copyright © 2018年 Archer. All rights reserved.
//

import Foundation

/// 任意节点v到根节点有且仅有唯一一条路径
/// 任意节点v的深度 = 节点v到根节点的路径长度(也就是边数，亦即度)
/// depth(v) = |path(v)|
/// path(v)以上的节点均称为v的祖先
/// path(v)以下的节点均称为v的后代

/// 树的半线性：在任一深度，节点v的祖先若存在，则必然唯一，然而，若节点v的后代存在却未必唯一

/// 根节点是所有节点的公共祖先，深度为0(depth(root) = 0)
/// 树中没有后代的节点称为叶子节点，叶子节点是必然存在的，否则就是一棵拥有无穷多个节点的树了

/// 所有叶子节点中深度最大者，称为树的高度 height(v) = height(subtree(v))
/// 对于只有一个节点(也就是只有根节点)的树来说，它的depth = 0, 因此 height也等于0
/// 特别的对于空树，它的height/depth = -1


/// 注意到 depth(v) + height(subtree(v)) <= height(r)
/// 也就是说树中任一节点v的深度和以v作为根节点的子树的高度之和不会大于此树的高度


///               R
///        ---------------
///        ↓      ↓      ↓
///        A      B      C
///      ------          ↓
///      ↓    ↓          F
///      D    E     -----------
///                 ↓    ↓    ↓
///                 G    H    K
///    注意到一棵树内各个节点的出度(亦即直接后代数)
///    可以将其改进为 每个节点只与自己的第一个孩子节点直接通信
///    由第一个孩子节点去管理它的兄弟 （长子+兄弟）
///    这样的话，纵向上都是firstChild，横向上都是nextSibling
///
///    R
///    ↓
///    A --→ B --→ C
///    ↓           ↓
///    D --→ E     F
///                ↓
///                G --→ H --→ K
///
///  这样转换之后就很有意思了 上图旋转45度就是一颗二叉树
///
///                    R
///                    ↓
///                    A
///                  ↙   ↘
///                 D     B
///                   ↘     ↘
///                    E     C
///                         ↙
///                       F
///                     ↙
///                   G
///                     ↘
///                       H
///                         ↘
///                           K
///
///  由此可见，二叉树虽然只是树这个全集中的一个子集，但是在施加了一些条件之后(有根有序)却可以用来表示所有的树结构
public final class BinaryTreeNode<Element> {
    
    public enum Color {
        case red
        case black
    }
    
    /// 高度
    var height: Int
    /// 颜色
    var color: Color
    /// 数据域
    var value: Element
    /// 左孩子
    var lchild: BinaryTreeNode<Element>?
    /// 右孩子
    var rchild: BinaryTreeNode<Element>?
    /// 父节点
    weak var parent: BinaryTreeNode<Element>?
    
    
    // 以当前节点为根节点的子树规模
    public var count: Int {
        get {
            // 计入自身
            var size = 1
            // 递归计入左子树规模
            if lchild != nil {
                size += lchild!.count
            }
            // 递归计入右子树规模
            if rchild != nil {
                size += rchild!.count
            }
            
            return size
        }
    }
    
    /// 中序遍历意义下的后继节点
    /// 对于二叉排序(搜索)树 它的中序遍历正好是排序的
    public var inOrderSuccessor: BinaryTreeNode<Element>? {
        get {
            var successor: BinaryTreeNode<Element>? = self
            // 如果有右孩子 那么肯定是右孩子为顶点的子树最左边的节点
            if successor?.rchild != nil {
                successor = successor?.rchild
                while successor?.lchild != nil {
                    successor = successor?.lchild
                }
            } else {
                // 不是根节点且是其父亲节点的右孩子
                // 按照中序遍历的规则
                while successor?.parent != nil && successor?.parent?.rchild === successor {
                    successor = successor?.parent
                }
                // 再往上一步 得到我们要的后继
                // 这一步也满足了successor一开始就是左孩子且没有右孩子的情况
                successor = successor?.parent
            }

            return successor
        }
    }

    init(_ value: Element, _ height: Int = 0, _ color: Color = .red) {
        self.value = value
        self.color = color
        self.height = height
    }
    
    /// 作为左孩子插入
    @discardableResult
    func insertAsLC(_ element: Element) -> BinaryTreeNode<Element> {
        // 假设self.lchild = nil
        lchild = BinaryTreeNode(element)
        lchild?.parent = self
        return lchild!
    }

    /// 作为右孩子插入
    @discardableResult
    func insertAsRC(_ element: Element) -> BinaryTreeNode<Element> {
        rchild = BinaryTreeNode(element)
        rchild?.parent = self
        return rchild!
    }
    
    /// 子树层次遍历
    func travLevel(_ body: (Element) throws -> Void) rethrows {
        /// 借助队列来实现
        let queue = Queue<BinaryTreeNode>()
        queue.enqueue(self)
        while !queue.isEmpty {
            let front = queue.dequeue()!
            try body(front.value)
            if let lchild = front.lchild {
                queue.enqueue(lchild)
            }
            if let rchild = front.rchild {
                queue.enqueue(rchild)
            }
        }
    }
    
    /// 子树先序遍历
    func travPre(_ body: (Element) throws -> Void) rethrows {
        #if true
        let stack = Stack<BinaryTreeNode>()
        var node: BinaryTreeNode? = self
        while node != nil || !stack.isEmpty {
            if let nd = node {
                // 访问当前节点
                try body(nd.value)
                // 当前节点入栈
                stack.push(nd)
                // 转向左孩子
                node = node?.lchild
            } else {
                // 没有左/右孩子 && 栈非空
                if !stack.isEmpty {
                    // 弹出栈顶元素
                    let nd = stack.pop()!
                    // 转向右孩子
                    node = nd.rchild
                }
            }
        }
        #else
        let stack = Stack<BinaryTreeNode>()
        var node: BinaryTreeNode? = self
        while node != nil || !stack.isEmpty {
            if let nd = node {
                // 访问当前节点
                try body(nd.value)
                // 转向其左孩子
                node = nd.lchild
                // 右孩子存在则入栈
                if let right = nd.rchild {
                    stack.push(right)
                }
            } else {
                // 没有左孩子的时候取出右孩子
                node = stack.pop()
            }
        }
        #endif
    }
    
    /// 子树中序遍历
    func travIn(_ body: (Element) throws -> Void) rethrows {
        /// 算法核心：访问左侧链上的节点，遍历右子树
        /// 右子树又是一个二叉树，重复上部操作
        let stack = Stack<BinaryTreeNode>()
        var node: BinaryTreeNode? = self
        while node != nil || !stack.isEmpty {
            if let nd = node {
                // 当前节点入栈
                stack.push(nd)
                // 转向左孩子
                node = node?.lchild
            } else {
                // 没有左/右孩子 && 栈非空
                if !stack.isEmpty {
                    // 访问栈顶元素
                    let nd = stack.pop()!
                    try body(nd.value)
                    // 转向右孩子
                    node = nd.rchild
                }
            }
        }
    }
    
    /// 子树后序遍历
    func travPost(_ body: (Element) throws -> Void) rethrows {
        // 根据后序遍历的规则和栈的原理
        // 比较巧妙 不需要记录出栈的次数
        let stack = Stack<BinaryTreeNode>()
        // 当前节点入栈
        stack.push(self)
        // 记录上一个出栈的元素
        var lastTop: BinaryTreeNode?
        while !stack.isEmpty {
            // 查看栈顶元素
            var node = stack.top!
            // 只有一下两种情况才会出栈
            // 1、当前节点没有左孩子也没有右孩子 这个比较好理解
            // 2、上一个出栈的元素是当前节点的左孩子或右孩子 对后序遍历来说，访问当前节点的时候肯定是从它的左孩子或右孩子返回
            if (node.lchild == nil && node.rchild == nil) ||
                (node.lchild === lastTop || node.rchild === lastTop) {
                node = stack.pop()!
                lastTop = node
                try body(node.value)
            } else {
                // 这里入栈的顺序不能改变
                // 这样就能保证出栈的时候只要有左孩子就先出左孩子
                if let rchild = node.rchild {
                    stack.push(rchild)
                }
                if let lchild = node.lchild {
                    stack.push(lchild)
                }
            }
        }
    }
}

extension BinaryTreeNode: Equatable where Element: Equatable {
    public static func == (lhs: BinaryTreeNode<Element>, rhs: BinaryTreeNode<Element>) -> Bool {
        return lhs.value == rhs.value
    }
}

extension BinaryTreeNode: Comparable where Element: Comparable {
    public static func < (lhs: BinaryTreeNode<Element>, rhs: BinaryTreeNode<Element>) -> Bool {
        return lhs.value < rhs.value
    }
}
